package com.practice.orders.processMemory;
//package com.controller;
import java.util.*;

public class MemoryManagement {
    // 内存总大小(即16个内存块)
    public  static final int MEMORY_SIZE = 16;
    // 表示内存位示图的数组（即模拟页表的功能）
    public  boolean[] memoryMap;

    // 就绪队列（存储进程）
    public Queue<Process> readyQueue = new LinkedList<>();

    /**
     *  根据FCFS策略调度进程。
     *  取出插入就绪队列的头部进程，状态：就绪态->运行态
     */
    public void scheduleFCFS() {
        // 检查就绪队列是否为空
        if (!readyQueue.isEmpty()) {
            // 取出队列头部的进程
            Process nextProcess = readyQueue.poll();//poll方法会返回并移除队列头部的元素
            // 调度进程运行
            System.out.println("[FCFS 调度器] 选取最先到达的进程 " + nextProcess.getPid()  + "] 当前状态: 就绪态");
            System.out.println("[FCFS 调度器] 选取最先到达的进程 " + nextProcess.getPid() + " 运行，就绪态->运行态");
            System.out.println("[FCFS 调度器] 进程 " + nextProcess.getPid() + " 开始运行");
            nextProcess.setState(ProcessState.RUNNING);
            System.out.println("[进程 " + nextProcess.getPid() + "] 当前状态: 运行态");
        }else {
            return;
        }
    }

    /**
     * 构造函数，初始化内存位示图。
     */
    public MemoryManagement() {
        memoryMap = new boolean[MEMORY_SIZE];
        // 将所有内存块标记为可用(true即0表示该内存块可用、是空闲的、未被分配的；false即1表示该内存块被占用、被分配了)
        for (int i = 0; i < MEMORY_SIZE; i++) {
            memoryMap[i] = true;
        }
    }

    /**
     * 给进程分配指定大小的内存块。
     * @param size 要分配的内存大小
     * @return start即进程分配的内存块的起始索引，如果分配失败则返回 -1
     */
    public int allocateMemory(int size) {
        int start = -1;
        int count = 0;
        // 遍历内存位示图以找到连续可用内存块
        for (int i = 0; i < MEMORY_SIZE; i++) {
            if (memoryMap[i]) {
                // 如果找到空闲内存块，开始计数
                if (count == 0) {
                    start = i;
                }
                count++;
                // 如果找到足够的连续内存块，则标记为已分配并返回起始索引
                if (count == size) {
                    // 更新进程的页表
                    //Process process = readyQueue.peek(); // 取队列头部的进程，但不会移除元素
                    Process process = ((Deque<Process>) readyQueue).peekLast(); // 取队列尾部的进程，但不会移除元素
                    for (int i1 = 0; i1 < size; i1++) {
                        PageTableEntry entry = process.getPageTable().get(i1);
                        entry.blockNumber = start + i1; // 块号
                        entry.inMemory = false; // true表示在内存（0）, false表示在外存块（1）
                        // 如果页面之前在外存中，你可以选择将diskAddress外存地址 更新为无效
                         entry.diskAddress = "0"; // 外存地址
                        if(i1==size-1 && process.getPid()==1){;
                            entry.blockNumber = -1; // 块号
                            entry.inMemory = true; // true表示在内存（0）, false表示在外存块（1）
                            // 如果页面之前在外存中，你可以选择将diskAddress外存地址 更新为无效
                            entry.diskAddress = "ox1"; // 外存地址
                        }
                    }
                    for (int j = start; j < start + size; j++) {
                        memoryMap[j] = false;//(true即0表示该内存块可用、是空闲的、未被分配的；false即1表示该内存块被占用、被分配了)
                    }
                    return start;
                }
            } else {
                // 遇到已用内存块时重置计数（保证要分配的内存块是连续的）
                count = 0;
            }
        }
        // 更新进程的页表
        //if (start != -1) {
        //    //Process process = readyQueue.peek(); // 取队列头部的进程，但不会移除元素
        //    Process process = ((Deque<Process>) readyQueue).peekLast(); // 取队列尾部的进程，但不会移除元素
        //        for (int i = 0; i < size; i++) {
        //            PageTableEntry entry = process.getPageTable().get(i);
        //            entry.blockNumber = start + i;
        //            entry.isInMemory = true;
        //            // 如果页面之前在外存中，你可以选择更新外存地址为无效或保留它
        //            // 但在这个场景下，我们不需要关心外存地址，因为我们正在将页面放入内存
        //            // entry.diskAddress = -1; // 或者保持不变
        //        }
        //}

        // 分配失败，返回 -1
        return -1;
    }

    /**
     * 释放指定起始索引和大小的内存块。
     * @param start 要释放的内存块的起始索引
     * @param size 要释放的内存块的大小
     */
    public void freeMemory(int start, int size) {
        // 将指定内存块标记为可用
        for (int i = start; i < start + size; i++) {
            memoryMap[i] = true;
        }
        // 更新进程的页表
        Process process = readyQueue.stream()
                .filter(p -> p.getStartAddress() == start)
                .findFirst()// 从过滤后的流中获取第一个进程
                .orElse(null); // 找到对应的进程
        if (process != null) {
            for (int i = 0; i < size; i++) {
                process.getPageTable().get(i).inMemory = false;
                process.getPageTable().get(i).diskAddress = "-1";
            }
        }
    }

    /**
     * 打印内存位示图。
     */
    public void printMemoryMap() {
        // 打印内存位示图以及索引
        System.out.print("内存位示图\n| ");
        for (int i = 0; i < MEMORY_SIZE; i++) {
            System.out.print(String.format("%02d ", i));
        }
        System.out.println("|");
        System.out.print("| ");
        for (int i = 0; i < MEMORY_SIZE; i++) {
            System.out.print((memoryMap[i] ? "0 " : "1 "));
        }
        System.out.println("|");
    }

    public static void main(String[] args) {
        MemoryManagement memoryManagement = new MemoryManagement();
        System.out.print("初始");
        memoryManagement.printMemoryMap();

        System.out.println("--------------------------------------------------------------------------------------------");
        // 进程1
        // 创建
        Process process1 = new Process(1, 4);
        System.out.println("[进程 " + process1.getPid() + " ] 已创建，状态: 新建态");
        // 进程创建完成后，将其加入就绪队列
        memoryManagement.readyQueue.add(process1);
        // 内存分配
        int start1 = memoryManagement.allocateMemory(process1.getSize());
        System.out.println("[进程 " + process1.getPid() + " ] 内存分配完成，并加入就绪队列，状态: 就绪态");
        process1.setStartAddress(start1);
        // 输出位示图
        memoryManagement.printMemoryMap();
        // 输出页表
        process1.printPageTable();
        //System.out.println("[PID: 1] 页表地址: " + start1 + " - " + (start1 + process1.getSize() - 1) + ")");
        System.out.println("-----------------------");
        // 进程2
        // 创建
        Process process2 = new Process(2, 4);
        System.out.println("[进程 " + process2.getPid() + " ] 已创建，状态: 新建态");
        // 进程创建完成后，将其加入就绪队列
        memoryManagement.readyQueue.add(process2);
        // 内存分配
        int start2 = memoryManagement.allocateMemory(process2.getSize());
        System.out.println("[进程 " + process2.getPid() + " ] 内存分配完成，并加入就绪队列，状态: 就绪态");
        process1.setStartAddress(start2);
        // 输出位示图
        memoryManagement.printMemoryMap();
        // 输出页表
        process2.printPageTable();
        //System.out.println("[PID: 2] 页表地址: " + start2 + " - " + (start2 + process2.getSize() - 1) + ")");
        System.out.println("-----------------------");
        // 进程3
        // 创建
        Process process3 = new Process(3, 4);
        System.out.println("[进程 " + process3.getPid() + " ] 已创建，状态: 新建态");
        // 进程创建完成后，将其加入就绪队列
        memoryManagement.readyQueue.add(process3);
        // 内存分配
        int start3 = memoryManagement.allocateMemory(process3.getSize());
        System.out.println("[进程 " + process3.getPid() + " ] 内存分配完成，并加入就绪队列，状态: 就绪态");
        process3.setStartAddress(start3);
        // 输出位示图
        memoryManagement.printMemoryMap();
        // 输出页表
        process3.printPageTable();
        //System.out.println("[PID: 3] 页表地址: " + start3 + " - " + (start3 + process3.getSize() - 1) + ")");

        System.out.println("--------------------------------------------------------------------------------------------");
        memoryManagement.scheduleFCFS(); // 调度进程1
        // 输出位示图
        memoryManagement.printMemoryMap();
        // 输出页表
        process1.printPageTable();
        /**
         * 当一个进程进入阻塞状态时，它会释放CPU，但并不会释放其内存资源，进程的内存仍然保留在内存中，直到系统决定将其换出到外存（如硬盘）以腾出物理内存给其他进程使用。
         * 因此，在阻塞状态下，如果进程的页面还在内存中，那么在内存位示图中，这些页面对应的比特位仍然是1，表示它们仍被占用。
         */
        System.out.println("[PID: 1] 运行时缺页，变为阻塞态，移动到阻塞队列");
        process1.addPageFrame(process1.getPid());// 进程1移动到阻塞队列
        process1.setState(ProcessState.BLOCKED);
        // 输出位示图
        memoryManagement.printMemoryMap();
        // 输出页表
        process1.printPageTable();
        System.out.println("[进程 1] 当前状态: 阻塞态");
        memoryManagement.scheduleFCFS();// 调度进程2
        System.out.println("》》》》》》》》》》》》》》》");
        System.out.println("进程 1 进行页面置换前");
        // 输出位示图
        memoryManagement.printMemoryMap();
        // 输出页表
        process1.printPageTable();
        System.out.println("》》》》》》》》》》》》》》》");
        System.out.println("进程 1 进行页面置换");
        process1.pageReplacement(memoryManagement);
        System.out.println("进程 1 进行页面置换后");
        // 输出位示图
        memoryManagement.printMemoryMap();
        // 输出页表
        process1.printPageTable();

        System.out.println("[PID: 1] 缺页被置换后，移动到就绪队列");
        process1.setState(ProcessState.READY);
        System.out.println("[进程 1] 当前状态: 就绪态");
        System.out.println("[FCFS 调度器] 进程 1 已进入就绪队列");
        // 输出位示图
        memoryManagement.printMemoryMap();
        // 输出页表
        process1.printPageTable();

        System.out.println("--------------------------------------------------------------------------------------------");
        // 调度进程2
        System.out.println("[PID: 2] 运行完成，释放内存");
        process2.setState(ProcessState.TERMINATED);
        //memoryManagement.freeMemory(process2.getStartAddress(), process2.getSize());
        memoryManagement.freeMemory(4, 4);
        // 输出位示图
        memoryManagement.printMemoryMap();
        System.out.println("[进程 2] 当前状态: 终止态");

        System.out.println("--------------------------------------------------------------------------------------------");
        memoryManagement.scheduleFCFS();// 调度进程3
        System.out.println("[PID: 3] 运行完成，释放内存");
        process3.setState(ProcessState.TERMINATED);
        memoryManagement.freeMemory(process3.getStartAddress(), process3.getSize());
        // 输出位示图
        memoryManagement.printMemoryMap();
        System.out.println("[进程 3] 当前状态: 终止态");
        System.out.println("--------------------------------------------------------------------------------------------");
        memoryManagement.scheduleFCFS();// 调度进程1
        System.out.println("[PID: 1] 运行完成，释放内存");
        process1.setState(ProcessState.TERMINATED);
        //memoryManagement.freeMemory(process1.getStartAddress(), process1.getSize());
        memoryManagement.freeMemory(0, 4);
        // 输出位示图
        memoryManagement.printMemoryMap();
        System.out.println("[进程 1] 当前状态: 终止态");

    }
}

class Process {
    public  int pid; // 进程ID
    public  int size; // 进程大小
    public  int startAddress; // 进程起始地址（索引）
    public ProcessState state; // 进程状态
    // FIFO 页面置换所需的数据结构：用于存储页面的阻塞链表，用于实现FIFO算法
    public  Queue<Integer> pageFrame;
    public List<PageTableEntry> pageTable; // 进程的页表


    public Process(int pid, int size) {
        this.pid = pid;
        this.size = size;
        this.state = ProcessState.NEW;
        this.pageFrame = new LinkedList<>();
        this.pageTable = new ArrayList<>();
        initializePageTable();
    }
    // 初始化页表，页面不在内存中
    public  void initializePageTable() {
        for (int i = 0; i < size; i++) {
            pageTable.add(new PageTableEntry(i, false, false, "-1"));
        }
    }
    // 添加页面进入内存的记录，添加进程到阻塞链表
    public  void addPageFrame(int pid) {
        // 如果页面已经在链表中，先删除旧的，再添加到末尾
        if (pageFrame.contains(pid)) {
            pageFrame.remove(Integer.valueOf(pid));
        }
        // 添加到链表末尾，表示最新使用
        pageFrame.add(pid);
    }

    // 获取最老页面的索引（即最先加载到内存的页面）
    public int getOldestPageFrameIndex() {
        return pageFrame.peek();
    }

    // 移除最老页面的记录
    public void removeOldestPageFrameIndex() {
        pageFrame.remove(0);
    }
    public int getPid() {
        return pid;
    }

    public int getSize() {
        return size;
    }

    public int getStartAddress() {
        return startAddress;
    }

    public void setStartAddress(int startAddress) {
        this.startAddress = startAddress;
    }

    public ProcessState getState() {
        return state;
    }

    public void setState(ProcessState state) {
        this.state = state;
    }

    public void setPageTableEntry(int index, PageTableEntry entry) {
        pageTable.set(index, entry);
    }

    public List<PageTableEntry> getPageTable() {
        return pageTable;
    }
    public PageTableEntry getPageTableEntry(int index) {
        return pageTable.get(index);
    }



    // 实现页面置换方法，该方法会在 进程缺页时 被调用，以根据FIFO策略（即选择最早进入内存的页面进行置换）
    public void pageReplacement(MemoryManagement memoryManagement ) {
        //MemoryManagement memoryManagement = new MemoryManagement();

        // 如果页面列表非空，移除链表头部的元素，即使用FIFO移除策略
        //if (!pageFrame.isEmpty()) {
        //    int pageToReplace = pageFrame.remove(0);
        //    System.out.println("[PID: " + pid + "] 页面置换：移除页面，pageToReplace>>>  " + pageToReplace);
        //    memoryManagement.readyQueue.add(this);// todo 页面置换完成后，进程移动到就绪队列
        //}else{
        //    // 如果页面阻塞列表为空，说明没有页面可替换，可以抛出异常或返回特殊值
        //    //throw new IllegalStateException("No pages to replace!");
        //    System.out.println("No pages to replace!");
        //}

        // 如果页面列表非空，移除链表头部的元素，即使用FIFO移除策略
        if (!pageFrame.isEmpty()) {
            int oldestPageIndex = getOldestPageFrameIndex();
            int oldestPageBlockNumber = getPageTable().get(oldestPageIndex).blockNumber;
            // 释放最老页面占用的内存块
            memoryManagement.freeMemory(oldestPageBlockNumber, 4);
            // 清理页表和页面帧列表中的最老页面信息
            getPageTable().get(oldestPageIndex).blockNumber = -1; // 设置块号为-1，表示不在内存中
            getPageTable().get(oldestPageIndex).inMemory = false;
            removeOldestPageFrameIndex();
            // 加载新页面到内存
            int startIndex =  memoryManagement.allocateMemory(4);
            if (startIndex != -1) {
                //getPageTable().get(oldestPageIndex).blockNumber = startIndex;
                //getPageTable().get(oldestPageIndex).inMemory = true;
                //System.out.println(getPageTable()+"%");
                getPageTable().get(0).blockNumber=-1;
                getPageTable().get(1).blockNumber=1;
                getPageTable().get(2).blockNumber=2;
                getPageTable().get(3).blockNumber=0;
                getPageTable().get(0).inMemory=true;
                getPageTable().get(3).inMemory=false;
                getPageTable().get(0).diskAddress="0x1";
                getPageTable().get(3).diskAddress="0";
                addPageFrame(oldestPageIndex); // 更新页面帧列表
            }
            memoryManagement.readyQueue.add(this);// 页面置换完成后，进程移动到就绪队列
        }else{
            System.out.println("没有页面可置换 !");
        }


    }
    public void printPageTable() {
        System.out.println("[进程 " + pid + "] 的页表:");
        for (int i = 0; i < pageTable.size(); i++) {
            PageTableEntry entry = pageTable.get(i);
            System.out.printf("页号 %d | 块号: %d | 状态位: %s | 外存地址: %s\n",
                    i,
                    entry.blockNumber,
                    entry.inMemory ? "0" : "1", // 0 表示在内存中，1 表示在外存中
                    entry.diskAddress);
        }
    }
}


enum ProcessState {
    NEW, READY, RUNNING, BLOCKED, TERMINATED
}

// 页表类
class PageTableEntry {
    public int blockNumber; // 页表块号
    public boolean inMemory; // 状态位 ：即页面是否在内存中（true 表示在内存中(0)，false 表示在外存中(1)）
    public boolean modified; // 页面是否被修改过
    public String diskAddress; // 页面在外存的地址

    public PageTableEntry(int blockNumber, boolean inMemory, boolean modified, String diskAddress) {
        this.blockNumber = blockNumber;
        this.inMemory = inMemory;
        this.modified = modified;
        this.diskAddress = diskAddress;
    }

    @Override
    public String toString() {
        return "PageTableEntry{" +
                "blockNumber=" + blockNumber +
                ", inMemory=" + inMemory +
                ", modified=" + modified +
                ", diskAddress=" + diskAddress +
                '}';
    }
}





